#include <string>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
    //剑指 Offer 50. 第一个只出现一次的字符
    char firstUniqChar(string s) {
        int hash[26] = {0};
        for (auto& ch : s)
        {
            ++hash[ch-'a'];
        }
        for (auto& ch : s)
        {
            if (hash[ch-'a'] == 1)
                return ch;
        }
        return ' ';
    }

    //剑指 Offer 32 - I. 从上到下打印二叉树
    vector<int> levelOrder(TreeNode* root) {
        if (root == nullptr)
        {
            return {};
        }
        
        vector<int> ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            TreeNode* cur =  q.front();
            q.pop();

            ans.push_back(cur->val);

            if (cur->left)
                q.push(cur->left);
            if (cur->right)
                q.push(cur->right);
        }

        return ans;
    }

    //剑指 Offer 32 - II. 从上到下打印二叉树 II
    vector<vector<int>> levelOrderII(TreeNode* root) {
        if (root == nullptr)
        {
            return {};
        }

        vector<vector<int>> ans;
        queue<TreeNode*> q;

        q.push(root);
        while (!q.empty())
        {
            vector<int> tmp;
            int size = q.size();
            
            for (int i = 0; i<size; ++i)
            {
                TreeNode* cur = q.front();
                q.pop();
                tmp.push_back(cur->val);

                if (cur->left)
                    q.push(cur->left);
                if (cur->right)
                    q.push(cur->right);
            }

            ans.push_back(tmp);
        }
        return ans;
    }

};